package main.二叉树;

import common.TreeNode;

/**
 * @author tmh
 * @date 2024/7/20 15:36
 * @description
 */
public class T437路径总和III {

    /**
     * 树的遍历+dfs
     * 一个朴素的做法是搜索以每个节点为根的（往下的）所有路径，并对路径总和为 targetSum 的路径进行累加统计。
     * <p>
     * 使用 dfs1 来搜索所有节点，复杂度为 O(n)；在 dfs1 中对于每个当前节点，使用 dfs2 搜索以其为根的所有（往下的）路径，同时累加路径总和为 targetSum 的所有路径，复杂度为 O(n)。
     * <p>
     * 作者：宫水三叶
     * 链接：https://leetcode.cn/problems/path-sum-iii/solutions/1021490/gong-shui-san-xie-yi-ti-shuang-jie-dfs-q-usa7/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param root
     * @param targetSum
     * @return
     */
    int count, number;
    public int pathSum(TreeNode root, int targetSum) {
        number=targetSum;
        dfs1(root);
        return count;
    }

    private void dfs1(TreeNode root) {
        if (root == null) {
            return;
        }
        //中左右，中就是dfs2的逻辑
        dfs2(root,root.val);
        dfs1(root.left);
        dfs1(root.right);
    }

    private void dfs2(TreeNode root, long sum) {
        if (sum == number) {
            count++;
        }
        if (root.left!=null){
            dfs2(root.left, sum + root.left.val);
        }
        if (root.right!=null){
            dfs2(root.right, sum + root.right.val);
        }
    }

}
